import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/21 11:16
 * @description 拓扑排序，寻找有向无边图中是否存在环，注意拓扑排序并不唯一，特殊情况下，没有一条边，那么所有的点都可以作为起点
 * 实现一、DFS
 */
public class Solution {
    public static void main(String[] args) {

    }

    /**
     * 存储有向图
     */
    List<Integer>[] edges;
    /**
     * 标记每个节点的状态，0-未搜索 1-搜索中 2-已完成
     */
    int[] visited;
    /**
     * 用数组来模拟栈，下标n-1为栈底，0为栈顶
     */
    int[] result;
    /**
     * 判断有向图中是否有环
     */
    boolean valid = true;
    /**
     * 栈下标
     */
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edges[i] = new ArrayList<>();
        }
        visited = new int[numCourses];
        result = new int[numCourses];
        index = numCourses - 1;
        for (int[] info : prerequisites) {
            edges[info[1]].add(info[0]);
        }
        // 每次挑选一个为搜索的节点，开始进行深度优先遍历
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        if (!valid) {
            return new int[0];
        }
        // 如果没有环，那么返回拓扑排序的内容
        return result;
    }
    public void dfs(int u) {
        // 将节点标记为搜索中
        visited[u] = 1;
        // 搜索其他节点，发现有环，立即停止搜索
        for (int v: edges[u]) {
            // 如果未搜索，那么dfs
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }else if (visited[v] == 1){
                // 如果搜索中，说明找到了环
                valid = false;
                return;
            }
        }
        // 将节点标记为已完成
        visited[u] = 2;
        // 将节点入栈
        result[index--] = u;
    }


}
